import java.util.Stack;

//验证栈序列
//https://leetcode.cn/problems/validate-stack-sequences/
public class Test {
    public static void main(String[] args) {
        //
        int[] pushed = new int[]{1,2,3,4,5};
        int[] popped = new int[]{4,5,3,2,1};
        Solution solution = new Solution();
        System.out.println(solution.validateStackSequences(pushed, popped));
    }
}


//方法一：自己写的
class Solution1 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //
        Stack<Integer> stack = new Stack<Integer>();
        int n = pushed.length;
        int i = 0;//pushed数组
        int cur = 0;//poped数组
        while (i < n) {
            //先判断：栈空？
            if(stack.isEmpty()){//栈空，进栈
                stack.push(pushed[i]);
                if(stack.peek() == popped[cur]){
                    stack.pop();
                    cur++;
                }
                i++;

            }else if(!stack.isEmpty()&&stack.peek() == popped[cur]){
                /*stack.pop();//这里需要特别处理一下，因为可能连续出栈（拧巴的点：不会出现i在poped数组和pushed数组中不匹配的情况的，因为，个数上会互相牵制）
                i++;*/
                while (stack.peek() == popped[cur]){
                    stack.pop();

                    cur++;
                }
            }else {
                stack.push(pushed[i]);
                i++;
            }
        }
        //能到这里，说明，全部进栈了
        while(!stack.isEmpty()&&stack.peek() == popped[cur]){
            stack.pop();
            cur++;
        }
        boolean flag = stack.isEmpty();
        if(!flag){
            return false;
        }
        return true;
    }
}

//方法二：老师的写法，简单
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int n = pushed.length;
        int i = 0;
        for(int x : pushed){
            stack.push(x);
            while(!stack.isEmpty()&&stack.peek() == popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();//或者：return i == n;
    }
}